package com.captain.leetcode.排序算法;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/3/20 20:08
 */
public class QuickSort {

    public static void main(String[] args) {
        for (int i : new QuickSort(new int[]{5, 3, 2, 1, 4}).getQuickSort()) {
            System.out.println(i);
        }
    }

    private final int[] array;

    public QuickSort(int[] array) {
        this.array = array;
    }

    public void quickSort() {
        //左闭 右开
        int end = array.length;
        sort(0, end);
    }

    //123   0 1
    private void sort(int begin, int end) {
        //只有一个元素时,不需要排序了
        if (end - begin < 2) return;
        //确定轴点位置
        int mid = privotIndex(begin, end);
        //对子序列进行快速排序
        sort(begin, mid);
        sort(mid + 1, end);
    }

    private int privotIndex(int begin, int end) {
        //备份数据
        int pivot = array[begin];
        end--;

        while (begin < end) {
            //升序
            //右边开始
            while (begin < end) {
                if (pivot > array[end]) {
                    end--;
                } else {
                    array[begin] = array[end];
                    begin++;
                    break;
                }
            }

            while (begin < end) {
                //左边
                if (pivot < array[begin]) {
                    begin++;
                } else {
                    array[end] = array[begin];
                    end--;
                    break;
                }
            }
        }

//        while (begin < end) {
//            //先从右侧开始
//            //右边的元素大于轴点元素时
//            while (begin < end) {
//                if (pivot < array[end]) {
//                    end--;
//                } else {
//                    array[begin] = array[end];
//                    begin++;
//                    break;
//                }
//            }
//            while (begin < end) {
//                //从左侧开始遍历
//                if (pivot > array[begin]) {
//                    begin++;
//                } else {
//                    array[end] = array[begin];
//                    end--;
//                    break;
//                }
//            }
//        }
        //将轴点元素放入最终位置
        array[begin] = pivot;
        return begin;
    }

    /**
     * des:
     * 获取排序好的数据
     *
     * @return {@link int[] }
     * @author captain
     * @date 2022/3/20 20:11
     */
    public int[] getQuickSort() {
        quickSort();
        return array;
    }
}
